In many applications, robots are used to perform functions in place of humans or to assist humans in order to increase productivity and efficiency. One such application is order fulfillment, which is typically performed in a large warehouse filled with products to be shipped to customers who have placed their orders over the internet for home delivery. Fulfilling such orders in a timely, accurate and efficient manner is logistically challenging to say the least.
In an online Internet shopping application, for example, clicking the “check out” button in a virtual shopping cart creates an “order.” The order includes a listing of items that are to be shipped to a particular address. The process of “fulfillment” involves physically taking or “picking” these items from a large warehouse, packing them, and shipping them to the designated address.
An important goal of the order fulfillment process is thus to ship as many items in as short a time as possible. The process of receiving an order, planning its fulfillment, finding the storage shelf or bin, picking the product, and repeating the process for each item on the order, then delivering the order to a shipping station is repetitive and labor intensive. In a warehouse stocked with thousands or tens of thousands of items of rapidly turning inventory, robots play a critical role in ensuring timely and efficient order fulfillment. In addition, the products that will ultimately be shipped first need to be received in the warehouse and stored or “placed” in storage bins in an orderly fashion throughout the warehouse so they can be readily retrieved for shipping.
Using robots to perform picking and placing functions may be done by the robot alone or with the assistance of human operators. Picking and placing or stocking functions, whether or not performed with human interaction, requires that the robot navigate from its present location to a target product storage or “bin” location. Along the robot's goal path from present location to product storage bin, the robot typically encounters stationary and moving obstacles such as walls, shelves, support structure, humans and other robots. As new product is stocked and depleted, as new shelves and bins are added and removed, and as miscellaneous objects are introduced into a shared human-robot space, the dynamic nature of an order fulfillment warehouse requires constant updating of information about the warehouse and its contents.
One method of navigation by a robot in an order fulfillment warehouse employs a spatial model or “map” of the warehouse, locally stored and updated by the robot, to allow the robot to operate autonomously or semi-autonomously as it performs its assigned order fulfillment tasks. The map is a digital representation of the warehouse, its storage locations, obstacles and other features. To arrive at a product bin in the presence of stationary and dynamic obstacles, the robot performs processing operations on the map to determine its present location and for continually recalibrating its movement along the goal path.
Various techniques may be used to create and maintain such maps, for example, using local laser scans or imaging from sensors on the robot as it navigates about the warehouse. Typically, the updating of maps in a robotic mapping application is achieved using Simultaneous Mapping and Location or “SLAM”. As the name suggests SLAM finds a robot's present location while simultaneously updating its map. However, SLAM is susceptible to pose errors due to uncertainties in robot obstacle sensing, robot control and location sensing, and the mapping process itself. Conventional methods for preventing such errors are computationally expensive.
What is needed is a computationally efficient method for reducing the computation time for determining pose using SLAM maps, thus improving navigation of the robot along the goal path. Such efficiency results in faster, smoother navigation to product storage bins, thus increasing the overall throughput of the order fulfillment warehouse.